# -*- coding: utf-8 -*-
# author: AZJ
# date: 2024/11/9
# 假如命运扼住了你的咽喉，你就去挠她的咯吱窝
def fact(n):
    nums = 1
    for i in range(1, n+1):
        nums *= i
    return nums
class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        '''方法一、C(m+n-2, m-1)
        (m+n-2)!/(n-1)!*(m-1)!'''
        # fact_total = fact(m+n-2)
        # fact_right = fact(n-1)
        # fact_left = fact(m-1)
        # return int(fact_total/(fact_right*fact_left))
        '''方法二
        m * n, 可以向右或向下, m是y轴, n是x轴
        向右走 n 步, 向下走 m 步, 可以到达终点
        dp[i][j] 表示走到(i,j)有多少种方式'''
        dp = [[1] * n] + [[1] + [0] * (n - 1) for _ in range(m - 1)]
        for i in range(m):
            for j in range(n):
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        print(dp[-1][-1])

if __name__ == '__main__':
    solution = Solution()
    # print([[1] + [0] * (5 - 1) for _ in range(3 - 1)])
    dp = [[1] + [0] * (3 - 1) for _ in range(5-1)]
    print(dp)